package binaryTree;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    //二叉树结点静态类
    static class TreeNode {
        public char val;
        public TreeNode left = null;//左孩子的引用
        public TreeNode right = null;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }


    //创建一棵二叉树 返回这棵树的根节点
    public static TreeNode createTree() {
        TreeNode root = new TreeNode('A');
        TreeNode node1 = new TreeNode('B');
        TreeNode node2 = new TreeNode('C');
        TreeNode node3 = new TreeNode('D');
        TreeNode node4 = new TreeNode('E');
        TreeNode node5 = new TreeNode('F');
        TreeNode node6 = new TreeNode('G');
        TreeNode node7 = new TreeNode('H');
        TreeNode node8 = new TreeNode('I');
        TreeNode node9 = new TreeNode('J');
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node3.right = node7;
        node4.left = node8;
        node8.left = node9;

        return root;
    }

    // 前序遍历
    public static void preOrder(TreeNode root) {
        if(root == null){
            return;
        }

        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    public static void inOrder(TreeNode root) {
        if(root == null){
            return;
        }

        preOrder(root.left);
        System.out.print(root.val + " ");
        preOrder(root.right);
    }

    // 后序遍历
    public static void postOrder(TreeNode root) {
        if(root == null){
            return;
        }

        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val + " ");
    }

    public static int nodeSize = 0;
    //获取树中节点的个数：遍历思路
    public static void size(TreeNode root) {
        if(root == null){
            return ;
        }
        //按前序遍历统计节点个数
        nodeSize++;
        size(root.left);
        size(root.right);
    }

    //获取节点的个数：子问题的思路
    public static int size2(TreeNode root) {
        //空树，返回0个结点
        if(root == null){
            return 0;
        }
        //一克数的节点数 = 根结点数 + 左子树的节点数 + 右子树的结点数
        return 1 + size2(root.left) + size2(root.right);
    }

    //获取叶子节点的个数：遍历思路
    public static int leafSize = 0;
    public static void getLeafNodeCount1(TreeNode root) {
        if(root == null){
            return;
        }
        //按前序遍历统计叶子节点
        //一个节点没有左右子树，则该节点是叶子节点
        if(root.left == null && root.right == null){
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    //获取叶子节点的个数：子问题
    public static int getLeafNodeCount2(TreeNode root) {
        //空树没有叶子节点，返回0
        if(root == null){
            return 0;
        }
        //一个节点没有左右子树，则该节点是叶子节点,返回1
        if(root.left == null && root.right == null){
            return 1;
        }
        //一棵树的叶子节点数 = 左子树的叶子节点数 + 右子树的叶子节点数
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }


    //获取第K层节点的个数
    public static int getKLevelNodeCount(TreeNode root, int k) {
        //空树，没有结点，返回0
        if(root == null){
            return 0;
        }
        //一个结点非空，且处于k层，返回1
        if(root != null && k == 1){
            return 1;
        }
        //第k层的节点数 = 左子树的k-1层的结点数 + 右子树的k-1层的节点数
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }


//    获取二叉树的高度
//    时间复杂度：O(N)
    public static int getHeight(TreeNode root) {
        if(root == null){
            return 0;
        }

        int leftHeight = 1 + getHeight(root.left);
        int rightHeight = 1 + getHeight(root.right);
        //一棵树的高度 = 左右子树中的最高的一棵树的高度
        return Math.max(leftHeight, rightHeight);
    }

    // 检测值为value的元素是否存在
    public static TreeNode find(TreeNode root, char val) {
        //空树，返回空，不存在
        if(root == null){
            return null;
        }
        //根节点的值等于所给定的值，返回根节点
        if(root.val == val){
            return root;
        }
        //左子树找
        TreeNode ret1 = find(root.left, val);
        //找到返回找到的结点
        if(ret1 != null && ret1.val == val){
            return ret1;
        }
        //右子树找
        TreeNode ret2 = find(root.right, val);
        //找到返回找到的结点
        if(ret2 != null && ret2.val == val){
            return ret2;
        }
        //未找到返回空
        return null;
    }

    //层序遍历
    public static void levelOrder(TreeNode root) {
        //空树直接返回，不用遍历
        if(root == null){
            return;
        }
        //创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        //将根节点入栈
        queue.offer(root);
        //遍历队列
        while(!queue.isEmpty()){
            //取出队头
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            //左子树非空，入队
            if(node.left != null){
                queue.offer(node.left);
            }
            //右子树非空，入队
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        System.out.println();
    }


    // 判断一棵树是不是完全二叉树
    public static boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node = null;
        queue.offer(root);
        while(!queue.isEmpty()){
            //将队头元素出队，并记录队头
            node = queue.poll();
            //左右子树均非空，左右入队
            if(node.left != null && node.right != null ){
                queue.offer(node.left);
                queue.offer(node.right);
                continue;
            }
            //左子树是空，右子树非空，则不是完全二叉树，返回false
            if(node.left == null && node.right != null){
                return false;
            }
            //左子树非空，右子树是空，跳出循环进入第二阶段进行检查
            if(node.left != null && node.right == null){
                break;
            }
        }
        //第二阶段检查剩余结点是否是叶子结点，如果存在非叶子结点，则不是完全二叉树
        while(!queue.isEmpty()){
            node = queue.poll();
            //存在非叶子结点，不是完全二叉树，返回false
            if(node.left != null || node.right != null){
                return false;
            }
        }
        //到此，说明该树是完全二叉树，返回true
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = createTree();

        preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);
        System.out.println();
        size(root);
        System.out.println(nodeSize);
        System.out.println(size2(root));

        getLeafNodeCount1(root);
        System.out.println(leafSize);
        System.out.println(getLeafNodeCount2(root));

        System.out.println(getKLevelNodeCount(root, 4));
        System.out.println(getHeight(root));

        TreeNode node = find(root, 'F');
        System.out.println(node);
        System.out.println(node == null ? null : node.val);

        levelOrder(root);

        System.out.println(isCompleteTree(root));


    }
}
